二叉树的右视图

发表于 | 分类于 |
字数统计: 313 字 | 阅读时长 ≈ 1 分钟

题目描述：给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

示例 1:

img

输入: [1,2,3,null,5,null,4]
输出: [1,3,4]

示例 2:
输入: [1,null,3]
输出: [1,3]

示例 3:
输入: []
输出: []

广度优先遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
var rightSideView = function(root) {
  let res = []
  if(!root) return res
  let queue = [root]
  while(queue.length) {
    let size = queue.length
    let level = []
    while(size--) {
      let node = queue.shift()
      level.push(node.val)
      if(node.left) {
        queue.push(node.left)
      }      
      if(node.right) {
        queue.push(node.right)
      }
    }
    res.push(level[level.length - 1]) // 较层次遍历的修改 res.push(level)
  }
  return res
};

复杂度分析

  • 时间复杂度：O(N)
  • 空间复杂度：O(n)

深度优先遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var rightSideView = function(root) {
  let res = []
  if(!root) return res
  dfs(root, 1, res)
  return res
};

var dfs = function(root, level, res) {
  if(!root) return 
  // 较层次递归的修改  res[level -1].push(root.val)
  if(!res[level - 1]) res[level - 1] = root.val
  // 更改遍历顺序，先从右边开始, 当右边没了, 再轮到左边
  if(root.right) {
    dfs(root.right, level + 1, res)
  }
  if(root.left) {
    dfs(root.left, level + 1, res)
  }
}

复杂度分析

  • 时间复杂度：O(N)
  • 空间复杂度：O(h)，h 是树的高度